/*
 * @lc app=leetcode.cn id=688 lang=cpp
 *
 * [688] “马”在棋盘上的概率
 */

// @lc code=start
class Solution
{
    int dirs[8][2] = {
        {-2, -1},
        {-2, 1},
        {2, -1},
        {2, 1},
        {-1, -2},
        {-1, 2},
        {1, -2},
        {1, 2},
    };

public:
    double knightProbability(int n, int k, int row, int column)
    {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));

        for (int step = 0; step <= k; step++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (step == 0)
                    {
                        dp[step][i][j] = 1;
                    }
                    else
                    {
                        for (auto &dir : dirs)
                        {
                            int ni = i + dir[0];
                            int nj = j + dir[1];
                            if (ni < 0 || ni >= n || nj < 0 || nj >= n)
                            {

                                continue;
                            }
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8.0;
                        }
                    }
                }
            }
        }

        return dp[k][row][column];
    }
};
// @lc code=end
